

def bellman_ford(edges, n_vertices, start):
    # 初始化距离数组，将源点到自身的距离设为 0，其他顶点设为无穷大
    distances = [float('inf')] * n_vertices
    distances[start] = 0

    # 进行 m - 1 次松弛操作
    for _ in range(n_vertices - 1):
        for u, v, w in edges:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # 检查负权回路
    for u, v, w in edges:
        if distances[u] != float('inf') and distances[u] + w < distances[v]:
            print("图中存在负权回路，无法计算最短路径。")
            return None

    return distances

# 示例使用
edges = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]
num_vertices = 5
source = 0

result = bellman_ford(edges, num_vertices, source)
if result:
    for i, dist in enumerate(result):
        print(f"从源节点 {source} 到节点 {i} 的最短距离是: {dist}")
